package com.xmg.dataStructure.digui;

/**
 * 8皇后问题算法实现
 */
public class Queue8 {
    static int max  = 8;
    static int[] array = new int[max];
    static int nums = 0;
    static int checkNums = 0;
    public static void main(String[] args) {
        check(0);
        System.out.printf("共有%d种解法",nums);
        System.out.printf("共尝试了%d次",checkNums);
    }

    static void check(int n){
        if(n==8){
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            array[n] = i;
            if (isPutted(n)){
                check(n+1);
            }
        }
    }

    static boolean isPutted(int n){
        checkNums++;
        for (int i = 0; i < n; i++) {
            if(array[i]==array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }

    static void print(){
        nums++;
        for (int i = 0; i < max; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}
